package com.hatricks.is.algorithm;

import java.util.Stack;

/**
 * @packageName: com.hatricks.is.algorithm
 * @className: LongestValidParentheses
 * @date: 2025-07-01 21:33
 * @description: 最长有效（格式正确且连续）括号子串的长度
 * <p>
 * <p>
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * * 示例 1：
 * * 输入：s = "(()"
 * * 输出：2
 * * 解释：最长有效括号子串是 "()"
 * * <p>
 * * 示例 2：
 * * 输入：s = ")()())"
 * * 输出：4
 * * 解释：最长有效括号子串是 "()()"
 * * <p>
 * * 示例 3：
 * * 输入：s = ""
 * * 输出：0
 * * <p>
 * * 示例 3：
 * * 输入：s = "(()(()()("
 * * 输出：4
 * * <p>
 * * 提示：
 * * <p>
 * * 0 <= s.length <= 30000
 * * s[i] 为 '(' 或 ')'
 */
public class LongestValidParentheses {

    public static void main(String[] args) {
        // 4
        System.out.println(longestValidParentheses("(()(()()("));
        // 2
        System.out.println(longestValidParentheses("(()"));
    }

    public static int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 初始基准点，表示有效子串开始的前一个位置
        int maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                // 遇到左括号，压入当前索引
                stack.push(i);
            } else {
                // 遇到右括号，弹出栈顶元素（可能是匹配的左括号或基准点）
                stack.pop();
                if (stack.isEmpty()) {
                    // 栈为空，说明当前右括号没有匹配的左括号
                    // 将其作为新的基准点
                    stack.push(i);
                } else {
                    // 栈不为空，计算当前有效子串长度
                    // i - stack.peek() 就是从基准点到当前位置的长度
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}
